#include <iostream>
#include <list>
#include <algorithm>
#include <future>

/**
 * FP: 函数化编程
 * splice用于将输入的首个元素放入结果列表中
 */
template<typename T>
std::list<T> sequential_quick_sort(std::list<T> input)
{
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(), input, input.begin());
    T const& pivot = *result.begin(); // 记录第一个
    // 将序列中分成小于组和大于组，使用lambda表达式确定区分标准
    auto divide_point = std::partition(input.begin(), input.end(), [&](T const& t) {
        return t < pivot;
    });

    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);

    auto new_lower(sequential_quick_sort(std::move(lower_part))); // 递归
    auto new_higher(sequential_quick_sort(std::move(input)));

    result.splice(result.end(), new_higher);
    result.splice(result.begin(), new_lower);

    return result;
}

template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
    if (input.empty()) {
        return input;
    }
    std::list<T> result;
    result.splice(result.begin(), input, input.begin());
    T const& pivot = *result.begin(); // 记录第一个
    // 将序列中分成小于组和大于组，使用lambda表达式确定区分标准
    auto divide_point = std::partition(input.begin(), input.end(), [&](T const& t) {
        return t < pivot;
    });

    std::list<T> lower_part;
    lower_part.splice(lower_part.end(), input, input.begin(), divide_point);

    std::future<std::list<T>> 
        new_lower(std::async(&parallel_quick_sort<T>, std::move(lower_part)));
    auto new_higher(parallel_quick_sort(std::move(input)));

    result.splice(result.end(), new_higher);
    result.splice(result.begin(), new_lower.get());

    return result;
}

// template<typename F, typename A>
// std::future<std::result_of<F(A&&)>::type> spawn_task(F&& f, A&& a)
// {
//     typedef std::result_of<F(A&&)>::type result_type;
//     std::packaged_task<result_type(A&&)> task(std::move(f));

//     std::future<result_type> res(task.get_future());
//     std::thread t(std::move(task), std::move(a));
//     t.detach();
//     return res;
// }


int main(int argc, char const *argv[])
{
    std::list<int> data = {3, 8, 2, 5, 9, 1, 0, 6, 7, 4};
    std::list<int> result = parallel_quick_sort(data);

    for (auto i : result) {
        std::cout << i << " ";
    }
    
    return 0;
}
